//给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。 
//
// 输入为 非空 字符串且只包含数字 1 和 0。 
//
// 
//
// 示例 1: 
//
// 
//输入: a = "11", b = "10"
//输出: "101" 
//
// 示例 2: 
//
// 
//输入: a = "1010", b = "1011"
//输出: "10101" 
//
// 
//
// 提示： 
//
// 
// 每个字符串仅由字符 '0' 或 '1' 组成。 
// 1 <= a.length, b.length <= 10^4 
// 字符串如果不是 "0" ，就都不含前导零。 
// 
//
// 
//
// 注意：本题与主站 67 题相同：https://leetcode-cn.com/problems/add-binary/ 
// Related Topics 位运算 数学 字符串 模拟 👍 2 👎 0


package leetcode.editor.cn1;

//Java：二进制加法
public class JFETK5 {
    public static void main(String[] args) {
        Solution solution = new JFETK5().new Solution();
        // TO TEST
        System.out.println(solution.addBinary("111", "1111"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String addBinary(String a, String b) {
            if (a == null || a.length() == 0 || b == null || b.length() == 0)
                return "";
            int ai = a.length() - 1, bi = b.length() - 1;
            int carry = 0;
            StringBuilder result = new StringBuilder("");
            while (ai >= 0 || bi >= 0) {
                char ach = ai >= 0 ? a.charAt(ai--) : '0';
                char bch = bi >= 0 ? b.charAt(bi--) : '0';
                // 对ach和bch进行相加
                int sum = ach - '0' + bch - '0' + carry;
                if (sum >= 2) {
                    sum = sum - 2;
                    carry = 1;
                } else {
                    carry = 0;
                }
                result.append(String.valueOf(sum));
            }
            if (carry == 1) {
                result.append(String.valueOf("1"));
            }
            // 对字符串进行反转
            return result.reverse().toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
